package leetcode.editor.cn;

/**
 * @author qidi
 * @date 2021-12-13 09:08:13
 */
class Q0807_MaxIncreaseToKeepCitySkyline {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxIncreaseKeepingSkyline(int[][] grid) {
            if (grid.length == 1 && grid[0].length == 1) return 0;

            int[] hori = new int[grid.length];
            int[] vert = new int[grid[0].length];

            for (int i = 0; i < grid.length; i++) {
                int maxH = 0;
                for (int j = 0; j < grid[0].length; j++) {
                    maxH = Math.max(maxH, grid[i][j]);
                    vert[j] = Math.max(vert[j], grid[i][j]);
                }
                hori[i] = maxH;
            }

            int heightSum = 0;

            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    heightSum += Math.min(hori[i], vert[j]) - grid[i][j];
                }
            }

            return heightSum;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0807_MaxIncreaseToKeepCitySkyline().new Solution();
        System.out.println(solution.maxIncreaseKeepingSkyline(new int[][]{
                {3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}
        }));
    }
}